#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 学生信息结构体
typedef struct Student
{
    char name[50];
    struct Student *next;
} Student;

// 创建学生节点并初始化
Student *createStudent(const char *name)
{
    // 分配内存,名为newStudent
    Student *newStudent = (Student *)malloc(sizeof(Student));
    if (newStudent == NULL)
    {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    strncpy_s(newStudent->name, name, sizeof(newStudent->name) - 1);
    newStudent->name[sizeof(newStudent->name) - 1] = '\0'; // 确保字符串以null结尾
    newStudent->next = NULL;
    return newStudent;
}

// 比较两个名字
int compareNames(const char *name1, const char *name2)
{
    return strcmp(name1, name2);
}

// 插入学生到链表中
void insertStudent(Student **head, const char *name)
{
    // 先给内存
    Student *newStudent = createStudent(name);

    // 头节点为空 或 前面的比后面的小
    if (*head == NULL || compareNames(newStudent->name, (*head)->name) < 0)
    {
        // 插入到链表头部
        newStudent->next = *head;
        *head = newStudent;
    }
    else
    {
        // 找到合适的位置插入
        Student *current = *head;
        while (current->next != NULL && compareNames(newStudent->name, current->next->name) >= 0)
        {
            current = current->next;
        }
        newStudent->next = current->next;
        current->next = newStudent;
    }
}

// 打印
void printList(Student *head)
{
    Student *current = head;
    while (current != NULL)
    {
        printf("%s\n", current->name);
        current = current->next;
    }
}

// 释放
void freeList(Student *head)
{
    Student *temp;
    while (head != NULL)
    {
        temp = head;
        head = head->next;
        free(temp);
    }
}

// 主函数
int main()
{
    Student *head = NULL;

    insertStudent(&head, "zhang_san");
    insertStudent(&head, "li_si");
    insertStudent(&head, "wang_wu");

    // 打印
    printList(head);

    // 释放
    freeList(head);

    return 0;
}